package com.dylan.历史.算法;

import com.dylan.历史.util.LogUtil;

/**
 * Created by Dylan on 2018/10/23.
 */
public class 回文字符串判断 {

    public static void main(String[] args) {
        LogUtil.info(judge1("abccba"));
        LogUtil.info(judge1("abcdcba"));
        LogUtil.info(judge1("abcdfcba"));
        LogUtil.info(judge2("a"));
        LogUtil.info(judge2("abccba"));
        LogUtil.info(judge2("abcdcba"));
        LogUtil.info(judge2("abcdfcba"));
    }

    /**
     * 判断是否是回文字符串
     */
    static boolean judge1(String str) {
        int l = str.length();
        int m = str.length() / 2;
        for (int i = 0; i <= m; i++) {
            if (str.charAt(i) != str.charAt(l - 1 - i)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 将字符串格式化为单链表后，再判断是否是回文字符串
     * 定位步骤：
     * a为慢指针，每次前进1步
     * b为块指针，每次前进2步
     * 当b不能再前进的时候，a的位置在中点附近
     * 使用k和p，来使a之前的部分反转
     * k表示前进之前a所处位置
     * p表示最后一个被反转的节点，即k之前的节点
     *
     * 判断步骤：
     * 如果b.next == null，说明有奇数个节点，否则为偶数个节点
     * p和q向相反方向查找判断
     */
    static boolean judge2(String str) {
        Node a = formatToLink(str);
        Node b = a;
        Node k = a;
        Node p = null;
        while (b.next != null && b.next.next != null) {
            a = a.next;
            b = b.next.next;
            k.next = p;
            p = k;
            k = a;
        }
        if (p == null) {
            return true;
        }
        // 确定两侧的起始位置
        Node l, r;
        if (b.next == null) {
            // 总共有奇数个节点，中间节点不需要判断
            r = k.next;
            l = p;
        } else {
            r = k.next;
            k.next = p;
            l = k;
        }
        // 判断
        while (l != null) {
            if (l.c != r.c) {
                return false;
            }
            l = l.next;
            r = r.next;
        }
        return true;
    }

    /**
     * 存储当前值和下一个节点
     */
    static class Node {
        char c;
        Node next;
        Node(char c, Node next) {
            this.c = c;
            this.next = next;
        }
    }

    /**
     * 将字符串格式化成单链表
     */
    static Node formatToLink(String str) {
        Node root = null;
        for (int i = str.length() - 1; i >= 0; i--) {
            root = new Node(str.charAt(i), root);
        }
        return root;
    }
}
